package algorithm.stack;

/**
 * leetcode : https://leetcode.com/problems/valid-parentheses/description/
 * Difficulty : Easy
 *
 * 输入一个字符串，只包含括号 "()","[]","{}" 这三种字符, 校验其中的括号全部都封闭
 * 例如：
 * Input:"()"       outPut:true
 * Input:"()[]"     outPut:true
 * Input:"{[]}"     outPut:true
 * Input:"([})"     outPut:false
 *
 * 利用栈的性质, 也就是数据结构里stack那一章讲的栈的用法
 * 左括号入栈，右括号匹配到左括号的话连带着左括号出栈，最后校验栈是否为空
 *
 * @Author Antony
 * @Since 2018/7/6 10:48
 */
public class ValidParentheses {

    public static void main(String[] args) {
        String s1 = "()[]{}";
        String s2 = "(])";
        System.out.println(isValid(s2));
    }


    // (leetcode beats 100%)
    public static boolean isValid(String s) {
        char[] stack = new char[s.length()];
        int stackPoint = 0;
        char tmp, c;
        for(int i=0; i<s.length(); i++){
            c = s.charAt(i);
            if(stackPoint > 0){
                tmp = stack[stackPoint-1];
                if(isPair(tmp, c)){ // 判断前一个元素和当前元素是否配对，如果配对则stackPoint--;
                    stackPoint--;
                }else{
                    stack[stackPoint++] = c;
                }
            }else{
                stack[stackPoint++] = c;
            }
        }
        return stackPoint == 0;
    }

    // 把判断配对的方法抽出来
    private static boolean isPair(char left, char right){
        if(left=='(' && right==')') return true;
        if(left=='[' && right==']') return true;
        if(left=='{' && right=='}') return true;
        return false;
    }
}
